package algorithm.interview.futu;

import java.util.*;


public class futu {
    /**
     * find topK in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public static int[] findTopKinTwoSortedArray (int[] arr1, int[] arr2, int k) {
        if (arr1.length == 0 || arr2.length == 0 || k <= 0) {
            return null;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>( (o1, o2) -> o2.num - o1.num );
        boolean[][] set = new boolean[arr1.length][arr2.length];
        int[] a = new int[k];

        int n1 = arr1.length-1;
        int n2 = arr2.length-1;
        int cur = 0;
        queue.add(new Node(n1, n2, arr1[n1]+arr2[n2]));
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            a[cur] = poll.num;
            n1 = poll.row;
            n2 = poll.col;
            if (cur == k-1) {
                break;
            }
            cur++;
            if (set[poll.row][poll.col] == false) {
                set[poll.row][poll.col] = true;
                if (n1 - 1 < 0 || n2 - 1 < 0)
                    continue;
                queue.add(new Node(n1, n2-1, arr1[n1]+arr2[n2-1]));
                queue.add(new Node(n1-1, n2, arr1[n1-1]+arr2[n2]));
            }
        }
        return a;
    }

    static class Node {
        int row;
        int col;
        int num;

        public Node(int row, int col, int num) {
            this.row = row;
            this.col = col;
            this.num = num;
        }
    }

    public static int solve (String nums) {
        // write code here
        return get(nums, 0);
    }

    public static int get(String nums, int index) {
        char[] chars = nums.toCharArray();
        if (chars.length == 0)
            return 0;
        if (index == chars.length-1)
            return 1;
        else if (index == chars.length-2)
            if (((int) chars[index] == 2+48 && (int)chars[index+1] <= 6+48) || ((int)chars[index] == 1+48))
                return 2;
            else
                return 1;

        if (( chars[index] == 2+48 && chars[index+1] <= 6+48) || (chars[index] == 1+48)) {
            return get(nums, index+2) + get(nums, index+1);
        } else {
            return get(nums, index+1);
        }
    }

    public static void main(String[] args) {
        int[] array = findTopKinTwoSortedArray(new int[]{1, 2, 3, 4, 5}, new int[]{3, 5, 7, 9, 11}, 25);
        for (int i = 0; i < 25; i++) {
            System.out.println(array[i]);
        }
//        System.out.println(solve("1234"));
    }
}